package 单调栈_上;

// 每日温度
// 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer
// 其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后
// 如果气温在这之后都不会升高，请在该位置用 0 来代替。
// 测试链接 : https://leetcode.cn/problems/daily-temperatures/

public class Code02_DailyTemperatures {

    public static int MAXN = 100001;

    // 存储的是 数组下标
    public static int[] stack = new int[MAXN];

    public static int r;

    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n]; //默认是0，则最后不需要进行清算，因为即使是进行清算也是填0
        r = 0; //栈指针
        for(int i = 0, cur; i < n; i++){
            // 求 两边小 ---》 “大 压 小”
            // 此时求 两边大 中的 右边大 ---》 “小 压 大”
            // 相较于模板：相等时候的处理，相等也加入单调栈
            while (r > 0 && temperatures[stack[r -1]] < temperatures[i]){
                cur = stack[--r];
                // 结算
                ans[cur] = i - cur;
            }
            stack[r++] = i;
        }
        return ans;
    }
}
